<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      计数排序使用一个用来存储每个元素在原始 数组中出现次数的临时数组。
      在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序 后的结果数组。
      
      */
      function countingSort(arr) {
        const { length } = arr;

        if (length < 2) {
          return arr;
        }
        // 寻找数组的最大值
        const maxValue = findMax(arr);
        // 临时数组
        const counts = new Array(maxValue + 1);

        /* 
        这个临时数组实际很巧妙 
        counts[item] 让arr的值变成了 counts的索引
        统计这个值出现的次数 作为 counts的值
        */
        arr.forEach((item) => {
          if (!counts[item]) {
            counts[item] = 0;
          }
          counts[item]++; // 如果出现了多次 那么让次数++
        });

        // 排序后的数组
        let newArr = [];
        let sortIndex = 0;
        counts.forEach((item, index) => {
          console.log(item, index);
          // 为了处理多次出现进行的循环
          while (item > 0) {
            newArr[sortIndex++] = index;
            item--;
          }
        });

        return newArr;
      }

      function findMax(arr) {
        let max = arr[0];
        for (let i = 1; i < arr.length; i++) {
          if (arr[i] > max) {
            max = arr[i];
          }
        }
        return max;
      }

      const res = countingSort([3, 9, 8, 1, 7, 8, 9, 10]);
      console.log(res);
    </script>
  </body>
</html>
